{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Strobogrammatic Number III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #array #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #数组 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: strobogrammaticInRange"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #中心对称数 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个字符串 low 和 high 表示两个整数 <code>low</code>&nbsp;和 <code>high</code> ，其中&nbsp;<code>low &lt;= high</code>&nbsp;，返回 范围 <code>[low, high]</code>&nbsp;内的 <strong>「中心对称数」</strong>总数&nbsp;&nbsp;。</p>\n",
    "\n",
    "<p><strong>中心对称数&nbsp;</strong>是一个数字在旋转了&nbsp;<code>180</code> 度之后看起来依旧相同的数字（或者上下颠倒地看）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> low = \"50\", high = \"100\"\n",
    "<strong>输出:</strong> 3 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> low = \"0\", high = \"0\"\n",
    "<strong>输出:</strong> 1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= low.length, high.length &lt;= 15</code></li>\n",
    "\t<li><code>low</code>&nbsp;和&nbsp;<code>high</code>&nbsp;只包含数字</li>\n",
    "\t<li><code>low &lt;= high</code></li>\n",
    "\t<li><code>low</code>&nbsp;and&nbsp;<code>high</code>&nbsp;不包含任何前导零，除了零本身。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [strobogrammatic-number-iii](https://leetcode.cn/problems/strobogrammatic-number-iii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [strobogrammatic-number-iii](https://leetcode.cn/problems/strobogrammatic-number-iii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"50\"\\n\"100\"', '\"0\"\\n\"0\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "        midChar = [\"\",\"0\",\"1\",\"8\"]\n",
    "        sideCharMap = {\"1\":\"1\",\"6\":\"9\",\"8\":\"8\",\"9\":\"6\"}\n",
    "        ans = 0\n",
    "        lowNum = int(low)\n",
    "        highNum = int(high)\n",
    "        \n",
    "        def dfs(mid):\n",
    "            nonlocal ans\n",
    "            # print(mid)\n",
    "            if (len(mid) > 0 and mid[0] != \"0\") or mid == \"0\":\n",
    "                midNum = int(mid)\n",
    "                if midNum >= lowNum and midNum <= highNum:\n",
    "                    ans += 1\n",
    "                if midNum >= highNum:\n",
    "                    return\n",
    "            for k,v in sideCharMap.items():\n",
    "                dfs(k+mid+v)\n",
    "            if len(mid) + 4 <= len(high):\n",
    "                dfs(\"0\" + mid + \"0\")\n",
    "\n",
    "        for midNum in midChar:\n",
    "            # print(midNum,midNum)\n",
    "            dfs(midNum)\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "        cnt = [0] * 15\n",
    "        cnt[1] = 3\n",
    "        for i in range(2, 15):\n",
    "            if i % 2:\n",
    "                cnt[i] = cnt[i - 1] * 3\n",
    "            else:\n",
    "                cnt[i] = 4 * 5 ** (i // 2 - 1)\n",
    "        acc = list(accumulate(cnt))\n",
    "\n",
    "        def turn(x):\n",
    "            d = {'1': '1', '6': '9', '8': '8', '0': '0', '9': '6'}\n",
    "            ans = ''\n",
    "            for ch in x:\n",
    "                ans += d[ch]\n",
    "            return ans\n",
    "\n",
    "        def f(x):\n",
    "            if x == '-1':\n",
    "                return 0\n",
    "            ln = len(x)\n",
    "            if ln == 1:\n",
    "                ret = 0\n",
    "                for k in [0, 1, 8]:\n",
    "                    if k <= int(x):\n",
    "                        ret += 1\n",
    "                return ret\n",
    "            res = acc[ln - 1] if ln > 1 else 0\n",
    "\n",
    "            @cache\n",
    "            def cal(i, islimited):\n",
    "                if i == (ln - 1) // 2 + 1:\n",
    "                    if ln % 2:\n",
    "                        if not islimited:\n",
    "                            return 1\n",
    "                        tmp = x[:i] + turn(x[:i - 1][::-1])\n",
    "                        if tmp > x:\n",
    "                            return 0\n",
    "                        return 1\n",
    "                    else:\n",
    "                        if not islimited:\n",
    "                            return 1\n",
    "                        tmp = x[:i] + turn(x[:i][::-1])\n",
    "                        if tmp > x:\n",
    "                            return 0\n",
    "                        return 1\n",
    "                ret = 0\n",
    "                down = 0 if i else 1\n",
    "                up = 9 if not islimited else int(x[i])\n",
    "                if ln % 2 and i == (ln - 1) // 2:\n",
    "                    for d in [0, 1, 8]:\n",
    "                        if down <= d <= up:\n",
    "                            ret += cal(i + 1, islimited and d == up)\n",
    "                else:\n",
    "                    for d in [0, 1, 6, 8, 9]:\n",
    "                        if down <= d <= up:\n",
    "                            ret += cal(i + 1, islimited and d == up)\n",
    "                return ret\n",
    "\n",
    "            res += cal(0, True)\n",
    "            return res\n",
    "\n",
    "        return f(high) - f(str(int(low) - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "        return self.strobogrammaticBelow(str(int(high)+1)) - \\\n",
    "            self.strobogrammaticBelow(low)\n",
    "    def strobogrammaticWithLength(self, n):\n",
    "        if n <= 0: return 1\n",
    "        return 5 ** (n // 2) * (3 if n % 2 else 1)\n",
    "    def strobogrammaticBelow(self, s):\n",
    "        if s == '0': return 0\n",
    "        print(s)\n",
    "        ds = [0, 1, 6, 8, 9]\n",
    "        ans = 1\n",
    "        for i in range(1, len(s)):\n",
    "            if i == 1:\n",
    "                ans += 2\n",
    "            else:\n",
    "                ans += 4 * self.strobogrammaticWithLength(i-2)\n",
    "            print(ans)\n",
    "        for i in range(len(s)//2):\n",
    "            for d in ds:\n",
    "                if i == 0 and d == 0:\n",
    "                    continue\n",
    "                if d >= int(s[i]):\n",
    "                    break\n",
    "                n = len(s) - (i+1) * 2\n",
    "                ans += self.strobogrammaticWithLength(n)\n",
    "            print(ans)\n",
    "            if int(s[i]) not in ds:\n",
    "                break\n",
    "        else:\n",
    "            if len(s) % 2:\n",
    "                for d in ds:\n",
    "                    if len(s) == 1 and d == 0:\n",
    "                        continue\n",
    "                    if d > int(s[len(s) // 2]):\n",
    "                        break\n",
    "                    if d == int(s[len(s) // 2]):\n",
    "                        t = s[:len(s)//2 + 1]\n",
    "                        for i in range(len(t)-2, -1, -1):\n",
    "                            if t[i] == '6':\n",
    "                                t = t + '9'\n",
    "                            elif t[i] == '9':\n",
    "                                t = t + '6'\n",
    "                            else:\n",
    "                                t = t + t[i]\n",
    "                        if t >= s:\n",
    "                            break\n",
    "                    ans += 1\n",
    "            else:\n",
    "                t = s[:len(s)//2]\n",
    "                for i in range(len(t)-1, -1, -1):\n",
    "                    if t[i] == '6':\n",
    "                        t = t + '9'\n",
    "                    elif t[i] == '9':\n",
    "                        t = t + '6'\n",
    "                    else:\n",
    "                        t = t + t[i]\n",
    "                if t < s:\n",
    "                    ans += 1\n",
    "        print(ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "        dic = {'0' : '0', '1' : '1', '8' : '8', '6' : '9', '9' : '6'}\n",
    "        res = 0\n",
    "        def dfs(cur):\n",
    "            if len(cur) > len(high):\n",
    "                return \n",
    "            if cur and int(cur) <= int(high) and int(cur) >= int(low):\n",
    "                nonlocal res \n",
    "                res += not (len(cur) > 1 and cur[-1] == '0') \n",
    "            for c in dic:\n",
    "                dfs(c + cur + dic[c])\n",
    "        dfs('0')\n",
    "        dfs('1')\n",
    "        dfs('8')\n",
    "        dfs('')\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pair = (('6','9'), ('9','6'), ('1','1'), ('8','8'), ('0','0'))\n",
    "# 中心确定 两边扩散\n",
    "ones = (\"0\", \"1\", \"8\", \"\")\n",
    "class Solution:\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(cur):\n",
    "            if len(low) <= len(cur) and len(cur) <= len(high):\n",
    "                if len(cur) == len(high) and cur > high:\n",
    "                    return\n",
    "                if (len(cur) == len(low) and cur >= low) or len(cur) > len(low):\n",
    "                    nonlocal ans\n",
    "                    if len(cur) == 1 or cur[0] != '0':\n",
    "                        ans += 1\n",
    "            if len(cur) + 2 <= len(high):\n",
    "                for k, v in pair:\n",
    "                    dfs(k + cur + v)\n",
    "        for s in ones:\n",
    "            dfs(s)\n",
    "        return ans                 \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s = [\"\", \"0\", \"1\", \"8\"]\n",
    "        self.l = [\"0\", \"1\", \"6\", \"8\", \"9\"]\n",
    "        self.r = [\"0\", \"1\", \"9\", \"8\", \"6\"]\n",
    "        self.ans  = 0\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "        for i in  range(len(self.s)):\n",
    "            self.dfs(self.s[i], low, high)\n",
    "        return self.ans\n",
    "        \n",
    "    def dfs(self, strnum, low, high):\n",
    "        if len(strnum) >= len(low) and len(strnum) <= len(high):\n",
    "            if  len(strnum) == len(high) and strnum > high:\n",
    "                return \n",
    "            if len(strnum) == len(low) and strnum < low :\n",
    "                return \n",
    "            if len(strnum) == 1 or strnum[0]!= '0':\n",
    "                self.ans += 1\n",
    "        if len(strnum) + 2 <= len(high):\n",
    "            for i in range(len(self.l)):\n",
    "                self.dfs(self.l[i] + strnum + self.r[i], low, high)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "      self.ret = 0\n",
    "      def dfs(curStr):\n",
    "        print(curStr)\n",
    "        if int(low) <= int(curStr) <= int(high):\n",
    "          self.ret += 1\n",
    "        if int(curStr) < int(high) and len(curStr)%2 == 0:\n",
    "          mid = len(curStr)//2\n",
    "          for newStr in ['0', '00', '1', '11', '8', '88', '69', '96']:\n",
    "            dfs(curStr[0:mid]+newStr+curStr[mid::])\n",
    "      for inistr in ['0', '1', '11', '8', '88', '69', '96']:\n",
    "        dfs(inistr)\n",
    "      return self.ret\n",
    "      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "        midChar = [\"\",\"0\",\"1\",\"8\"]\n",
    "        sideCharMap = {\"1\":\"1\",\"6\":\"9\",\"8\":\"8\",\"9\":\"6\"}\n",
    "        ans = 0\n",
    "        lowNum = int(low)\n",
    "        highNum = int(high)\n",
    "        \n",
    "        def dfs(mid):\n",
    "            nonlocal ans\n",
    "            # print(mid)\n",
    "            if (len(mid) > 0 and mid[0] != \"0\") or mid == \"0\":\n",
    "                midNum = int(mid)\n",
    "                if midNum >= lowNum and midNum <= highNum:\n",
    "                    ans += 1\n",
    "                if midNum >= highNum:\n",
    "                    return\n",
    "            for k,v in sideCharMap.items():\n",
    "                dfs(k+mid+v)\n",
    "            if len(mid) + 4 <= len(high):\n",
    "                dfs(\"0\" + mid + \"0\")\n",
    "\n",
    "        for midNum in midChar:\n",
    "            # print(midNum,midNum)\n",
    "            dfs(midNum)\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pair = {\n",
    "    '6':'9',\n",
    "    '9':'6',\n",
    "    '1':'1',\n",
    "    '8':'8',\n",
    "    '0':'0'\n",
    "}\n",
    "ones = (\"0\", \"1\", \"8\", \"\")\n",
    "class Solution:\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(cur):\n",
    "            if len(low) <= len(cur) and len(cur) <= len(high):\n",
    "                if len(cur) == len(high) and cur > high:\n",
    "                    return\n",
    "                if (len(cur) == len(low) and cur >= low) or len(cur) > len(low):\n",
    "                    nonlocal ans\n",
    "                    if len(cur) == 1 or cur[0] != '0':\n",
    "                        ans += 1\n",
    "            if len(cur) + 2 <= len(high):\n",
    "                for k, v in pair.items():\n",
    "                    dfs(k + cur + v)\n",
    "        for s in ones:\n",
    "            dfs(s)\n",
    "        return ans                 \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "        cnt = [0] * 15\n",
    "        cnt[1] = 3\n",
    "        for i in range(2, 15):\n",
    "            if i % 2:\n",
    "                cnt[i] = cnt[i - 1] * 3\n",
    "            else:\n",
    "                cnt[i] = 4 * 5 ** (i // 2 - 1)\n",
    "        acc = list(accumulate(cnt))\n",
    "\n",
    "        def turn(x):\n",
    "            d = {'1': '1', '6': '9', '8': '8', '0': '0', '9': '6'}\n",
    "            ans = ''\n",
    "            for ch in x:\n",
    "                ans += d[ch]\n",
    "            return ans\n",
    "\n",
    "        def f(x):\n",
    "            if x == '-1':\n",
    "                return 0\n",
    "            ln = len(x)\n",
    "            # if ln == 1:\n",
    "            #     ret = 0\n",
    "            #     for k in [0, 1, 8]:\n",
    "            #         if k <= int(x):\n",
    "            #             ret += 1\n",
    "            #     return ret\n",
    "            res = acc[ln - 1] if ln > 1 else 0\n",
    "\n",
    "            @cache\n",
    "            def cal(i, islimited):\n",
    "                if i == (ln - 1) // 2 + 1:\n",
    "                    if ln % 2:\n",
    "                        if not islimited:\n",
    "                            return 1\n",
    "                        tmp = x[:i] + turn(x[:i - 1][::-1])\n",
    "                        if tmp > x:\n",
    "                            return 0\n",
    "                        return 1\n",
    "                    else:\n",
    "                        if not islimited:\n",
    "                            return 1\n",
    "                        tmp = x[:i] + turn(x[:i][::-1])\n",
    "                        if tmp > x:\n",
    "                            return 0\n",
    "                        return 1\n",
    "                ret = 0\n",
    "                down = 0 if (i > 0 or ln == 1) else 1\n",
    "                up = 9 if not islimited else int(x[i])\n",
    "                if ln % 2 and i == (ln - 1) // 2:\n",
    "                    for d in [0, 1, 8]:\n",
    "                        if down <= d <= up:\n",
    "                            ret += cal(i + 1, islimited and d == up)\n",
    "                else:\n",
    "                    for d in [0, 1, 6, 8, 9]:\n",
    "                        if down <= d <= up:\n",
    "                            ret += cal(i + 1, islimited and d == up)\n",
    "                return ret\n",
    "\n",
    "            res += cal(0, True)\n",
    "            return res\n",
    "\n",
    "        return f(high) - f(str(int(low) - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "        begin = len(low)\n",
    "        end = len(high)\n",
    "\n",
    "\n",
    "        def helper(x):\n",
    "            pairs = [['1','1'],['8','8'],['6','9'],['9','6']]\n",
    "\n",
    "            if x == 0:\n",
    "                return ['']\n",
    "            if x == 1:\n",
    "                return ['0','1','8']\n",
    "            result = []\n",
    "            for n in helper(x-2):\n",
    "                for a,b in pairs:\n",
    "                    result.append(a+n+b)\n",
    "\n",
    "                if x != i :\n",
    "                    result.append('0' + n + '0')\n",
    "\n",
    "            return result\n",
    "        total = 0 \n",
    "        for i in range(begin,end+1):\n",
    "            x = helper(i)\n",
    "            if i == begin:\n",
    "                x = [y for y in x if int(y)>=int(low)]\n",
    "            if i == end:\n",
    "                x = [y for y in x if int(y)<=int(high)]\n",
    "            total += len(x)\n",
    "\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "        # 0 1 6 8 9\n",
    "        # 69-96 88 689\n",
    "        # 6-9 1-1 8-8 0-0\n",
    "        pair = [[6,9],[1,1],[8,8],[9,6]]\n",
    "        def helper(x, n):\n",
    "            if x == 0:\n",
    "                return ['']\n",
    "            if x == 1:\n",
    "                return ['0','1','8']\n",
    "            res = []\n",
    "            for each in helper(x-2, n):\n",
    "                for p in pair:\n",
    "                    res.append(str(p[0]) + each + str(p[1]))\n",
    "                if x != n:\n",
    "                    res.append('0' + each + '0')\n",
    "            return res\n",
    "        res = 0\n",
    "        for ll in range(len(low), len(high)+1):\n",
    "            curr_list = helper(ll, ll)\n",
    "            for each in curr_list:\n",
    "                if int(low) <= int(each) <= int(high):\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "        begin = len(low)\n",
    "        end = len(high)\n",
    "\n",
    "\n",
    "        def helper(x):\n",
    "            pairs = [['1','1'],['8','8'],['6','9'],['9','6']]\n",
    "\n",
    "            if x == 0:\n",
    "                return ['']\n",
    "\n",
    "            if x == 1:\n",
    "                return ['0','1','8']\n",
    "            result = []\n",
    "            for n in helper(x-2):\n",
    "                for a,b in pairs:\n",
    "                    result.append(a+n+b)\n",
    "\n",
    "                if x != i:\n",
    "                    result.append('0'+n+'0')\n",
    "\n",
    "            return result\n",
    "\n",
    "        total = 0\n",
    "\n",
    "        for i in range(begin,end+1):\n",
    "            x = helper(i)\n",
    "            if i == begin:\n",
    "                x = [y for y in x if int(y)>= int(low)]\n",
    "            if i == end:\n",
    "                x = [y for y in x if int(y)<= int(high)]\n",
    "            total += len(x)\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "        dict1 = {'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'}\n",
    "        n = len(high)\n",
    "        low, high = int(low), int(high)\n",
    "        res = set()\n",
    "        if int(low) < 10:\n",
    "            for k in [0, 1, 8]:\n",
    "                if low <= k <= high:\n",
    "                    res.add(k)\n",
    "\n",
    "        def helper(n):\n",
    "            nonlocal res\n",
    "            if n == 0:\n",
    "                return ['']\n",
    "            if n == 1:\n",
    "                return ['0', '1', '8']\n",
    "            ans = []\n",
    "            for i in helper(n - 2):\n",
    "                for k, v in dict1.items():\n",
    "                    tmp = v + i + k\n",
    "                    ans.append(tmp)\n",
    "                    if len(str(int(tmp))) == n and low <= int(tmp) <= high:\n",
    "                        res.add(tmp)\n",
    "            return ans\n",
    "\n",
    "        helper(n)\n",
    "        helper(n - 1)\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def helper(n, zero):\n",
    "    if not n:\n",
    "        return []\n",
    "    d = {'1': '1', '6': '9', '8': '8', '9': '6', '0': '0'}\n",
    "    if n == 1:\n",
    "        return ['0', '1', '8']\n",
    "    if n == 2:\n",
    "        return ['11', '69', '88', '96']\n",
    "    old_res = helper(n - 2, True)\n",
    "    if n == 4:\n",
    "        old_res.append('00')\n",
    "    new_res = []\n",
    "    for res in old_res:\n",
    "        for k, v in d.items():\n",
    "            if zero or k != '0':\n",
    "                new_res.append(k + res + v)\n",
    "    return new_res\n",
    "\n",
    "class Solution:\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "        lb = int(low)\n",
    "        rb = int(high)\n",
    "        s = set()\n",
    "        for n in range(len(low) - 1, len(high) + 1):\n",
    "            for num in helper(n, False):\n",
    "                if lb <= int(num) <= rb:\n",
    "                    s.add(int(num))\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "        def cal(n):\n",
    "            pairs = [['1', '1'], ['8', '8'], ['6', '9'], ['9', '6']]\n",
    "            def dfs(x):\n",
    "                if x == 0:\n",
    "                    return ['']\n",
    "                elif x == 1:\n",
    "                    return ['0', '1', '8']\n",
    "                res = []\n",
    "                for y in dfs(x - 2):\n",
    "                    for a, b in pairs:\n",
    "                        res.append(a + y + b)\n",
    "                    \n",
    "                    if x != n:\n",
    "                        res.append('0' + y + '0')\n",
    "                return res\n",
    "            return dfs(n)\n",
    "        n1, n2 = len(low), len(high)\n",
    "        mn, mx = min(n1, n2), max(n1, n2)\n",
    "        res = []\n",
    "        for n in range(mn, mx + 1):\n",
    "            for x in cal(n):\n",
    "                if int(low) <= int(x) <= int(high):\n",
    "                    res.append(x)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def func(self, n: int) -> List[str]:\n",
    "\n",
    "        self.pairs = [['1', '1'], ['8', '8'], ['6', '9'], ['9', '6']]\n",
    "\n",
    "        def dfs(x: int) -> List[str]:\n",
    "            if x == 0:\n",
    "                return [\"\"]\n",
    "            if x == 1:\n",
    "                return [\"0\", \"1\", \"8\"]\n",
    "            ans = []\n",
    "            for s in dfs(x - 2):\n",
    "                for a, b in self.pairs:\n",
    "                    ans.append(a + s + b)\n",
    "                if x != n:\n",
    "                    ans.append('0' + s + '0')\n",
    "            return ans\n",
    "\n",
    "        return dfs(n)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "        n1, n2 = len(low), len(high)\n",
    "        min_len = min(n1, n2)\n",
    "        max_len = max(n1, n2)\n",
    "        res = []\n",
    "\n",
    "        for n in range(min_len, max_len + 1):\n",
    "            for s in self.func(n):\n",
    "                if int(low) <= int(s) <= int(high):\n",
    "                    res.append(s)\n",
    "        return len(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "        # 先让0可以作为首位\n",
    "        dp = [[] for i in range(15)]\n",
    "        dp[0] = [\"0\", \"1\", \"8\"]\n",
    "        dp[1] = [\"96\", \"69\", \"11\", \"88\", \"00\"]\n",
    "\n",
    "        for i in range(2, 15):\n",
    "            for s in dp[i - 2]:\n",
    "                for zuhe in dp[1]:\n",
    "                    dp[i].append(zuhe[0] + s + zuhe[1])\n",
    "        low_num = 0\n",
    "        high_num = 0\n",
    "        mid_num = 0\n",
    "        for num in dp[len(low) - 1]:\n",
    "            if len(num) > 1 and num[0] != \"0\" and int(num) >= int(low) and int(num) <= int(high):\n",
    "                low_num += 1\n",
    "            if len(num) == 1 and int(num) >= int(low) and int(num) <= int(high):\n",
    "                low_num += 1\n",
    "\n",
    "        if len(high) > len(low):\n",
    "            for num in dp[len(high) - 1]:\n",
    "                if len(num) > 1 and num[0] != \"0\" and int(num) <= int(high) and int(num) >= int(low):\n",
    "                    high_num += 1\n",
    "                if len(num) == 1 and int(num) >= int(low) and int(num) <= int(high):\n",
    "                    high_num += 1\n",
    "\n",
    "        if len(high) > len(low) + 1:\n",
    "            for i in range(len(low), len(high) - 1):\n",
    "                mid_num += len(dp[i]) * 4 // 5\n",
    "\n",
    "        print(low_num, mid_num, high_num)\n",
    "        return low_num + high_num + mid_num\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "        pairs={'0':'0','1':'1','8':'8','6':'9','9':'6'}\n",
    "        self.dict={0:['']}\n",
    "        def dfs(x):\n",
    "            if x==1:\n",
    "                self.dict[x]=['0','1','8']\n",
    "                return ['0','1','8']\n",
    "            else:\n",
    "                ans=[]\n",
    "                for ch in self.dict[x-2]:\n",
    "                    for a,b in pairs.items():\n",
    "                        ans.append(a+ch+b)\n",
    "                self.dict[x]=ans\n",
    "                return ans\n",
    "        ans=0\n",
    "        for i in range(1,len(high)+1):\n",
    "            for x in dfs(i):\n",
    "                if not (len(x)>1 and x[0]=='0') and int(low)<=int(x)<=int(high):\n",
    "                    ans+=1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "        def gt(a,b):\n",
    "            if len(a)>len(b):\n",
    "                return True\n",
    "            elif len(a)<len(b):\n",
    "                return False\n",
    "            else:\n",
    "                return a>=b\n",
    "        def helper(num):\n",
    "            n = len(num)\n",
    "            dp = [[] for _ in range(n+1)]\n",
    "            dp[0]=['']\n",
    "            dp[1] = ['0','1','8']\n",
    "            if n==1:\n",
    "                return bisect_right(dp[1],num)\n",
    "            d = {'6':'9','9':'6','8':'8','1':'1','0':'0'}\n",
    "            dd = {'6':'9','9':'6','8':'8','1':'1'}\n",
    "            r = 3\n",
    "            for i in range(2,n+1):\n",
    "                for p in dp[i-2]:\n",
    "                    for j in dd:\n",
    "                        dp[i].append(j+p+d[j])\n",
    "                        if gt(num,dp[i][-1]):\n",
    "                            r+=1\n",
    "                    dp[i].append('0'+p+'0')\n",
    "            return r\n",
    "        def ishelper(num):\n",
    "            d = {'6':'9','9':'6','8':'8','1':'1','0':'0'}\n",
    "            if any(i not in d for i in num):\n",
    "                return False\n",
    "            for i in range(len(num)//2):\n",
    "                if d[num[i]]!=num[-i-1]:\n",
    "                    return False\n",
    "            if len(num)%2==1:\n",
    "                return num[len(num)//2] in '018'\n",
    "            return True\n",
    "        if high==low:\n",
    "            return ishelper(low)*1\n",
    "        return helper(high)-helper(low)  + ishelper(low)\n",
    "                    \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def help(self, n: int, depth: int) ->List[str]:\n",
    "        if n == 1:\n",
    "            return [\"0\", \"1\", \"8\"]\n",
    "        if n == 2:\n",
    "            ret = [\"11\", \"69\", \"96\", \"88\"]\n",
    "            if depth > 0:\n",
    "                ret.append(\"00\")\n",
    "            return ret\n",
    "        ret = self.help(n-2, depth+1)\n",
    "        ans = []\n",
    "        for val in ret:\n",
    "            ans.append(\"1\" + val + \"1\")\n",
    "            ans.append(\"6\" + val + \"9\")\n",
    "            ans.append(\"9\" + val + \"6\")\n",
    "            ans.append(\"8\" + val + \"8\")\n",
    "            if depth > 0:\n",
    "                ans.append(\"0\" + val + \"0\")\n",
    "        return ans\n",
    "\n",
    "    def strobogrammaticInRange(self, low: str, high: str) -> int:\n",
    "        ret = []\n",
    "        for i in range(len(low), len(high)+1):\n",
    "            ret.extend(self.help(i, 0))\n",
    "        ret.sort(key= lambda a: int(a))\n",
    "        #print(ret)\n",
    "        low_index = bisect.bisect_right(ret, int(low), key=lambda a: int(a) )\n",
    "        high_index = bisect.bisect_right(ret, int(high), key=lambda a: int(a) )\n",
    "        #print(high_index, \"  \", low_index)\n",
    "        if low in ret:\n",
    "            return high_index-low_index+1\n",
    "        return high_index-low_index"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
